Distributed systems formed a plurality of computers have widely been used in various fields. The distributed systems exist in a wide variety of forms. A cluster system in which all the computers behave as a computer can be cited as an exemplary distributed system. Cloud services that have rapidly spread are also provided with the distributed systems. For example, a distributed key-value store for storing the information by giving a name (key) to a value is used in the cloud service.
The same information is stored in a plurality of computers in order to improve fault tolerance. This prevents loss of information even when the data loss occurs in some of the computers. A technical problem to multiplex the information is how to maintain the consistency of the multiplexed information when the information is changed. The contents or results of the change are notified to each computer so that each computer applies the change. This method can maintain the consistency.
To perform this method, note that it is necessary to perform changes in the same order in each computer when the changes that are not commutative are simultaneously performed. For example, a change A to add 1,000 yen to a deposit balance and a change B to add 1% of the deposit balance to the deposit balance occur at almost the same time. The changes applied in different orders have the final results that are not identical. In other words, it is necessary to determine the order of the changes A and B and make all of the multiplexed computers perform the changes in the same order. Similarly, in a method in which the results from changes are notified to each computer, the order of the changes needs being the same in the computers.
To maintain the same order of the changes, it is necessary to put order numbers to all of the changes. If the request sources of the changes are unified, the request sources can put the order numbers. In general, however, the request sources are not necessarily unified. To determine the order of the changes when the request sources are not unified, a method is disclosed in ZooKeeper: A Distributed Coordination Service for Distributed Applications <URL: http://zookeeper.apache.org/doc/current/zookeeperOver.html>. According to the disclosed method, the change requests are temporarily collected in a computer referred to as a leader (or a master) so that the order of the change requests is determined.
However, when the master computer breaks down and stops in the method in which the change requests are collected in the master computer and the order of the change requests is determined, it is difficult to determine the order of the change requests until another computer is selected as the master computer. This halts the multiplexing process.